'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-17 15:54:33
'''
#
# @lc app=leetcode.cn id=117 lang=python3
#
# [117] 填充每个节点的下一个右侧节点指针 II
#

# @lc code=start
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        def func(last, n, new_start):
            if last:
                last.next=n
            if not new_start:
                new_start = n
            return n, new_start
        if not root:
            return None
        start=root
        while start:
            last, p, new_start=None, start, None
            while p:
                if p.left:
                    last, new_start = func(last, p.left, new_start)
                if p.right:
                    last, new_start = func(last, p.right, new_start)
                p=p.next
            start=new_start
        return root

        
# @lc code=end

